Manipulation of discrete time signals by means of digital coding has become a major tool in modern communications engineering. Coding is directed to such purposes as compression, noise rejection, and data security. Transform coding is one of the most common approaches.
A form of transform coding of continuous functions, orthonormal decomposition (and subsequent reconstruction), has been known since the time of Fourier. In recent years, discrete orthonormal transforms have been derived for applying analogous techniques and results to discrete time signals. Specific discrete orthonormal decompositions, for example, those using the (discrete) fast fourier transform (FFT) or the discrete cosine transform (DCT), are frequently used for electronic processing of many kinds of digitized univariate discrete time signals.
However, high speed and computational efficiency in coding and decoding of signals are key goals in designing a coding system. Methods of decomposing signals which are currently in use suffer from two inherent characteristics which limit either speed or computational efficiency or both.
The first limitation is that in FFT and DCT coding and in related systems, use of transcendental functions (e.g., sines and cosines) required in the generation of the transform coefficients generally requires copious multiplication and addition in floating point arithmetic, which is very time consuming even on high speed signal processing chips. The second major limitation is that all transform coding methods in use before the current invention, including those such as the Walsh-Hadamard transform which have binary valued coefficients (e.g., +1, -1), and do not therefore generally require floating point arithmetic, suffer from another generic limitation when used for compression purposes, namely the need for bit allocation, which is computation intensive.
One of the principal objectives in designing an efficient coding method for discrete time electronic signals is to effect a parsimonious representation of the signal. Parsimonious in this context implies minimization of the bandwidth or amount of electronic storage space necessary to store or transmit an acceptable representation or approximation of the signal.
Economy and efficiency in representation are achieved or enhanced by quantizing the transform domain coefficients--in the case of the FFT or DCT, the frequency domain coefficients. Quantization of the transform domain coefficients renders those coefficients in a much smaller number of bits than the number of bits in which the original (not-transformed) incoming signal is expressed. Quantization by itself and in combination with other properties of a given transform can produce significant compression in the representation of the signal, thereby economizing storage space or transmission bandwidth.
In addition, transforms of discrete time signals such as the DCT result automatically in frequency "binning." Other transforms such as Walsh-Hadamard, though not frequency based, nevertheless resolve the signal energy into a finite number of (non-frequency-based) transform domain bins.
Most discrete transform processing operates on time slices of the signal, called "frames," each containing a fixed number of samples of the signal. If a signal is rapidly varying in frequency or other transform domain content over time, for example an audio signal comprising music or speech, the energy in the signal is transformed to different subsets of bins in different time-separated samples of the signal depending on the varying spectrum--or transform domain content--of the incoming signal contained in the given frame. To achieve efficiency in use of digital processing resources, previous coding methods have had to address what has come to be known as the "bit allocation" problem.
The bit allocation problem arises as follows: if the coding system allocates to a transform domain bin with low energy content a number of bits equal to the number of bits allocated to a transform domain bin with a high energy content, a large fraction of the bits allocated to the low energy content bin are not mathematically significant (and therefore contain little information in the information theory sense) and hence need not be used or stored. Thus, the storage and processing resources in the low energy bins are not utilized efficiently. Bit allocation methodologies have been devised to address this situation.
For all orthogonal transform coding techniques, it has been shown that "the optimal bit allocation strategy is such that variances of all quantizer noise sources are equalized." P. P. Vaidyanathan, "Multirate Systems And Filter Banks" (PTR Prentice Hall, Inc., Englewood Cliffs, N.J. 1993), p. 821. The result is that in actual practice differing numbers of bits are assigned to different transform domain bins according to the transform domain energy content of the signal. If the transform domain energy distribution varies rapidly with time, the optimal bit allocation coding method just described ideally follows the variation with a rapidly changing bit allocation, preferably even on a frame by frame basis.
The computations necessary for optimizing bit allocation in transform coding can be quite complex, however. N. S. Jayant and P. Noll, "Digital Coding of Waveforms" (Prentice Hall, Inc., Englewood Cliffs, N.J. 1984), sections 12.4 and following. Optimization requires knowledge of the statistical properties of the incoming signal. Moreover, if bit allocation is to be adaptive, that is, if it is to follow closely a rapidly time-varying energy distribution, such as that of music or speech, the process is computationally intensive. In sophisticated applications, computing the bit allocation typically absorbs greater than one half of the computing power available for processing the signal.
The need for economy sometimes precludes performing such bit allocation calculations in real time. In some applications it is not technically or economically feasible to devote the computing resources necessary to perform bit allocation calculations every frame. As a result, bit allocation is far from optimal much of the time if the input signal power distribution is not nearly stationary.
Bit allocation which is frequently incorrect leads to a particularly vexing aliasing problem associated with binning. In this situation the aliasing error in a given frequency or transform domain bin is determined by the manner of quantizing adjacent bins. To solve this problem within the available computing resource allocation, engineers resort to methods to limit the distortion introduced into the reconstructed signal by the quantization at adjacent transform domain bins by differing numbers of bits.
Slowly varying bit allocation (i.e., not frame by frame) also fails to guarantee against data overflow in some transform domain bins. Indeed, if bit allocation is not done every frame, there is a significant likelihood of overflow in one or more transform domain bins. Overflow gives rise to non-linear clipping of the transform domain coefficient. Clipping can produce electronically and aesthetically significant distortion in the reconstructed output signal.
The two sources of distortion, aliasing and clipping, can produce significant and usually unrecoverable degradation in the reconstructed signal. There is thus a need for a transform coding technology which avoids the bit allocation problem altogether. The current invention avoids this problem altogether by spreading energy more or less evenly across transform domain bins so that bit allocation need not be time varying.
There are also some applications, e.g., spread spectrum transmission, in which it would be advantageous to spread the signal energy out more or less evenly among all the transform domain bins. One advantage of an appropriate method of energy spreading would be that no one transform domain coefficient is more significant than any other. In this case, the signal could be approximately reconstructed even if one or a few transmission bands were degraded or lost. In contrast, losing a high energy coefficient in a traditional transform coding technique (e.g., the DFT) would be catastrophic to reconstructing the signal. No prior coding method has been found which has such energy spreading properties and binary valued coefficients. In fact, the Walsh-Hadamard transform, which has one advantage of the present invention, namely binary valued coefficients, is particularly unsuitable for energy spreading: indeed, for a very broad class of natural input signals, the Walsh-Hadamard transform can be shown to have extremely uneven distribution of energy among transform domain bins.
An essential object of the present invention, therefore, is to provide a new method and apparatus for coding and decoding of digital signals which provide a representation of the input signal using a novel decomposition of the incoming signal that is not based on frequency. A further object is to provide a method of signal coding and decoding using a novel decomposition of the signal in which the dominant computations in the signal processing platform use only integer add and subtract operations, thereby providing a high degree of speed and efficiency in operation. It is a further object of the invention to provide a novel signal decomposition which spreads the energy of the incoming signal reasonably evenly over the transform domain bins. It is a further object of the invention to use the energy spreading property to enhance signal compression. It is another object of this invention to produce a coding method for discrete time signals for the compression application in which there is no bit allocation computation. It is yet another object of this invention to enable uniform quantization for all transform domain bins. It is yet a further object of this invention to produce a coding method for discrete time signals for the compression application which eliminates both adjacent bin aliasing and clipping of transform domain coefficients. It is another object of this invention to provide an energy spreading coding method which can be used in spread spectrum applications. It is yet a further object of this invention to provide an energy spreading filter bank which is a quadrature mirror filter.